/*
** $Id: ltablib.c,v 1.38.1.3 2008/02/14 16:46:58 roberto Exp $
** Library for Table Manipulation
** See Copyright Notice in lua.h
*/

#include <string.h>

#define ltable_c
#define LUA_CORE

#include "lua.h"

#include "lmem.h"
#include "lobject.h"
#include "lstate.h"
#include "ltable.h"


/*
** max size of array part is 2^MAXBITS
*/
#if LUAI_BITSINT > 26
#define MAXBITS	26
#else
#define MAXBITS	(LUAI_BITSINT - 2)
#endif

#define MAXASIZE	(1<<MAXBITS)


#define hashpow2(t, n)	(gnode(t, lmod((n), sizenode(t))))

#define hashstr(t, str)	hashpow2(t, (str)->tsv.hash)
#define hashboolean(t, p)	hashpow2(t, p)


/*
** for some types, it is better to avoid modulus by power of 2, as
** they tend to have many 2 factors.
*/
#define hashmod(t, n)	(gnode(t, (n) % ((sizenode(t)-1)|1)))


#define hashpointer(t, p)	hashmod(t, IntPoint(p))


/*
** number of ints inside a lua_Number
*/
#define numints	cast_int(sizeof(lua_Number)/sizeof(int))


#define dummynode	(&dummynode_)

static const Node dummynode_ = {
	{{NULL}, LUA_TNIL},	/* value */
	{{{NULL}, LUA_TNIL, NULL}}	/* key */
};


/*
** hash for lua_Numbers
*/
static Node *hashnum (const Table *t, lua_Number n) {
	unsigned int a[numints];
	int i;
	if (luai_numeq(n, 0))	/* avoid problems with -0 */
		return gnode(t, 0);
	memcpy(a, &n, sizeof(a));
	for (i = 1; i < numints; ++i) a[0] += a[i];
	return hashmod(t, a[0]);
}


/*
** returns the `main' position of an element in a table (that is, the index
** of its hash value)
*/
static Node *mainposition (const Table *t, const TValue *key) {
	switch(ttype(key)) {
		case LUA_TNUMBER:
			return hashnum(t, nvalue(key));
		case LUA_TSTRING:
			return hashstr(t, rawtsvalue(key));
		case LUA_TBOOLEAN:
			return hashboolean(t, bvalue(key));
		case LUA_TLIGHTUSERDATA:
			return hashpointer(t, pvalue(key));
		default:
			return hashpointer(t, gcvalue(key));
	}
}


/*
** returns the index for `key' if `key' is an appropriate key to live in
** the array part of the table, -1 otherwise.
*/
static int arrayindex (const TValue *key) {
	if (ttisnumber(key)) {
		lua_Number n = nvalue(key);
		int k;
		lua_number2int(k, n);
		if (luai_numeq(cast_num(k), n))
			return k;
	}
	return -1;
}


/*
** returns the index of a `key' for table traversals. First goes all
** elements in the array part, then elements in the hash part. The
** beginning of a traversal is signalled by -1.
*/
static int findindex (lua_State *L, Table *t, StkId key) {
	int i;
	if (ttisnil(key)) return -1;	/* first iteration */
	i = arrayindex(key);
	if (0 < i && i <= t->sizearray)	/* is `key' inside array part? */
		return i-1;	/* yes; that's the index (corrected to C) */
	else {
		Node *n = mainposition(t, key);
		do {	/* check whether `key' is somewhere in the chain */
			/* key may be dead already, but it is ok to use it in `next' */
			// TODO 未理解这个而if语句的判断条件
			if (luaO_rawequalObj(key2tval(n), key) ||
				(ttype(gkey(n)) == LUA_TDEADKEY && iscollectable(key) &&
				gcvalue(gkey(n)) == gcvalue(key))) {
				i = cast_int(n - gnode(t, 0));	/* key index in hash table */
				/* hash elements are numbered after array ones */
				return i + t->sizearray;
			}
			else n = gnext(n);
		} while(n);
	}
	// TODO luaG_runerror(L, "invalid key to " LUA_QL("next"));  /* key not found */
	return 0;
}


int luaH_next (lua_State *L, Table *t, StkId key) {
	int i = findindex(L, t, key);	/* find original element */
	for (i++; i < t->sizearray; i++) {	/* try first array part */
		if (!ttisnil(&t->array[i])) {	/* a non-nil value? */
			// TODO 没有理解以下两行的意义
			setnvalue(key, cast_num(i+1));
			setobj2s(L, key+1, &t->array[i]);
			return 1;
		}
	}
	for (i -= t->sizearray; i < sizenode(t); ++i) {	/* then hash part */
		if (!ttisnil(gval(gnode(t, i)))) {	/* a non-nil value? */
			// TODO 没有理解以下两行的意义
			setobj2s(L, key, key2tval(gnode(t, i)));
			setobj2s(L, key+1, gval(gnode(t, i)));
			return 1;
		}
	}
	return 0;
}


/*
** {=============================================================
** Rehash
** ==============================================================
*/

static int computesizes (int nums[], int *narray) {
	int i;
	int twotoi;	/* 2^i */
	int a = 0;	/* number of elements smaller than 2^i */
	int na = 0;	/* number of elements to go to array part */
	int n = 0; /* optimal size for array part */
	for (i = 0, twotoi = 1; twotoi / 2 <  *narray; i++, twotoi *= 2) {
		if (nums[i] > 0) {
			a += nums[i];
			if (a > twotoi/2) {	/* more than half elements present? */
				n = twotoi;
				na = a;	/* all elements smaller than n will go to array part */
			}
		}
		if (a == *narray) break;	/* all elements already counted */
	}
	*narray = n;
	lua_assert(*narray/2 <= na && na <= *narray);
	return na;
}


static int countint(const TValue *key, int *nums) {
	int k = arrayindex(key);
	if (0 < k && k <= MAXASIZE) {	/* is `key' an appropriate array index? */
		nums[ceillog2(k)]++;	/* count as such */
		return 1;
	}
	else
		return 0;
}


static int numusearray (const Table *t, int *nums) {
	int lg;
	int ttlg;	/* 2^lg */
	int ause = 0;	/* summation of `nums' */
	int i = 1;	/* count to traverse all array keys */
	for (lg = 0, ttlg = 1; lg <= MAXBITS; lg++, ttlg *= 2) {	/* for each slice */
		int lc = 0;	/* counter */
		int lim = ttlg;
		if (lim > t->sizearray) {
			lim = t->sizearray;	/* adjust upper limit */
			if (i > lim)
				break;	/* no more elements to count */
		}
		/* count elements in range (2^(lg-1), 2^lg] */
		for (; i <= lim; ++i) {
			if (!ttisnil(&t->array[i-1]))
				lc++;
		}
		nums[lg] += lc;
		ause += lc;
	}
	return ause;
}


static int numusehash (const Table *t, int *nums, int *pnasize) {
	int totaluse = 0;	/* total number of elements */
	int ause = 0;	/* summation of `nums' */
	int i = sizenode(t);
	while (i--) {
		Node *n = &t->node[i];
		if (!ttisnil(gval(n))) {
			ause += countint(key2tval(n), nums);
			totaluse++;
		}
	}
	*pnasize += ause;
	return totaluse;
}


static void setarrayvector (lua_State *L, Table *t, int size) {
	int i;
	luaM_reallocvector(L, t->array, t->sizearray, size, TValue);
	for (i = t->sizearray; i < size; ++i)
		setnilvalue(&t->array[i]);
	t->sizearray = size;
}


static void setnodevector (lua_State *L, Table *t, int size) {
	int lsize;
	if (size == 0) {	/* no elements to hash part? */
		t->node = cast(Node *, dummynode);
		lsize = 0;
	}
	else {
		int i;
		lsize = ceillog2(size);
		if (lsize > MAXBITS)
			// TODO luaG_runerror(L, "table overflow");
			return;
		size = twoto(lsize);
		t->node = luaM_newvector(L, size, Node);
		for (i = 0; i < size; ++i) {
			Node *n = gnode(t, i);
			gnext(n) = NULL;
			setnilvalue(gkey(n));
			setnilvalue(gval(n));
		}
	}
	t->lsizenode = cast_byte(lsize);
	t->lastfree = gnode(t, size);	/* all positions are free */
}


static void resize (lua_State *L, Table *t, int nasize, int nhsize) {
	int i;
	int oldasize = t->sizearray;
	int oldhsize = t->lsizenode;
	Node *nold = t->node;	/* save old hash ... */
	if (nasize > oldasize)	/* array part must grow? */
		setarrayvector(L, t, nasize);
	/* create new hash part with appropriate size */
	setnodevector(L, t, nhsize);
	if (nasize < oldasize) {	/* array part must shrink? */
		t->sizearray = nasize;
		/* re-insert elements from vanishing slice */
		for (i = nasize; i < oldasize; ++i) {
			if (!ttisnil(&t->array[i]))
				setobjt2t(L, luaH_setnum(L, t, i+1), &t->array[i]);
		}
		/* shrink array */
		luaM_reallocvector(L, t->array, oldasize, nasize, TValue);
	}
	/* re-insert elements from hash part */
	for (i = twoto(oldhsize) - 1; i >= 0; i--) {
		Node *old = nold + i;
		if (!ttisnil(gval(old)))
			setobjt2t(L, luaH_set(L, t, key2tval(old)), gval(old));
	}
	if (nold != dummynode)
		luaM_freearray(L, nold, twoto(oldhsize), Node);	/* free old array */
}


void luaH_resizearray (lua_State *L, Table *t, int nasize) {
	int nsize = (t->node == dummynode) ? 0 : sizenode(t);
	resize(L, t, nasize, nsize);
}


static void rehash (lua_State *L, Table *t, const TValue *ek) {
	int nasize, na;
	int nums[MAXBITS+1];	/* nums[i] = number of keys between 2^(i-1) and 2^i */
	int i;
	int totaluse;
	for (i = 0; i <= MAXBITS; ++i) nums[i] = 0;	/* reset counts */
	nasize = numusearray(t, nums);	/* count keys in array part */
	totaluse = nasize;
	totaluse += numusehash(t, nums, &nasize);
	/* count extra key */
	nasize += countint(ek, nums);
	totaluse++;
	/* compute new size for array part */
	na = computesizes(nums, &nasize);
	/* resize the table to new computed sizes */
	resize(L, t, nasize, totaluse - na);
}


/*
** }=============================================================
*/


Table *luaH_new (lua_State *L, int narray, int nhash) {
	Table *t = luaM_new(L, Table);
	// TODO luaC_link(L, obj2gco(t), LUA_TTABLE);
	t->metatable = NULL;
	t->flags = cast_byte(~0);
	/* temporary values (kept only if some malloc fails) */
	t->array = NULL;
	t->sizearray = 0;
	t->lsizenode = 0;
	t->node = cast(Node *, dummynode);
	setarrayvector(L, t, narray);
	setnodevector(L, t, nhash);
	return t;
}


void luaH_free (lua_State *L, Table *t) {
	if (t->node != dummynode)
		luaM_freearray(L, t->node, sizenode(t), Node);
	luaM_freearray(L, t->array, t->sizearray, TValue);
	luaM_free(L, t);
}


static Node *getfreepos (Table *t) {
	while (t->lastfree-- > t->node) {
		if (ttisnil(gkey(t->lastfree)))
			return t->lastfree;
	}
	return NULL;	/* could not find a free place */
}


/*
** inserts a new key into a hash table; first, check whether key's main
** position is free. If not, check whether colliding node is in its main
** position or not: if it is not, move colliding node to an empty place and
** put new key in its main position; otherwise (colliding node is in its main
** position), new key goes to an empty position.
*/
static TValue *newkey (lua_State *L, Table *t, const TValue *key) {
	Node* mp = mainposition(t, key);
	if (!ttisnil(gval(mp)) || mp == dummynode) {
		Node *othern;
		Node *n = getfreepos(t);	/* get a free place */
		if (n == NULL) {
			rehash(L, t, key);	/* grow table */
			return luaH_set(L, t, key);	/* re-insert key into grown table */
		}
		lua_assert(n != dummynode);
		othern = mainposition(t, key2tval(mp));
		if (othern != mp) {	/* is colliding node out of its main position? */
			/* yes; move colliding node into free position */
			while (gnext(othern) != mp) othern = gnext(othern);	/* find previous */
			gnext(othern) = n;	/* redo the chain with `n' in place of `mp' */
			*n = *mp;
			gnext(mp) = NULL;	/* now `mp' is free */
			setnilvalue(gval(mp));
		}
		else {	/* colliding node is in its own main position */
			/* new node will go into free position */
			gnext(n) = gnext(mp);
			gnext(mp) = n;
			mp = n;
		}
	}
	gkey(mp)->value = key->value; gkey(mp)->tt = key->tt;
	//TODO luaC_barriert(L, t, key);
	lua_assert(ttisnil(gval(mp)));
	return gval(mp);
}


const TValue *luaH_getnum (Table *t, int key) {
	/* (1 <= key && key <= t->sizearray) */
	if (cast(unsigned int, key-1) < cast(unsigned int, t->sizearray))
		return &t->array[key-1];
	else {
		lua_Number nk = cast_num(key);
		Node *n = hashnum(t, nk);
		do {	/* check whether `key' is somewhere in the chain */
			if (ttisnumber(gkey(n)) && luai_numeq(nvalue(gkey(n)), nk))
				return gval(n);	/* that's it */
			else n = gnext(n);
		} while(n);
		return luaO_nilobject;
	}
}


/*
** search function for strings
*/
const TValue *luaH_getstr(Table *t, TString *key) {
	Node *n = hashstr(t, key);
	do {	/* check whether `key' is somewhere in the chain */
		if (ttisstring(gkey(n)) && rawtsvalue(gkey(n)) == key)
			return gval(n);	/* that's it */
		else n = gnext(n);
	} while(n);
	return luaO_nilobject;
}


/*
** search function for integers
*/
const TValue *luaH_get (Table *t, const TValue *key) {
	switch (ttype(key)) {
		case LUA_TNIL: return luaO_nilobject;
		case LUA_TSTRING: return luaH_getstr(t, rawtsvalue(key));
		case LUA_TNUMBER: {
			int k;
			lua_Number n = nvalue(key);
			lua_number2int(k, n);
			if (luai_numeq(cast_num(k), nvalue(key))) /* index is int? */
				return luaH_getnum(t, k);	/* use specialized version */
			/* else go through */

		}
		default: {
			Node *n = mainposition(t, key);
			do {	/* check whether `key' is somewhere in the chain */
				if (luaO_rawequalObj(key2tval(n), key))
					return gval(n);	/* that's it */
				else n = gnext(n);
			} while(n);
			return luaO_nilobject;
		}
	}
}


TValue *luaH_set (lua_State *L, Table *t, const TValue *key) {
	const TValue *p = luaH_get(t, key);
	t->flags = 0;
	if (p != luaO_nilobject)
		return cast(TValue*, p);
	else {
		if (ttisnil(key)) return NULL; //TODO luaG_runerror(L, "table index is nil");
		else if (ttisnumber(key) && luai_numisnan(nvalue(key)))
			return NULL;
			//TODO luaG_runerror(L, "table index is NaN");
		return newkey(L, t, key);
	}
}


TValue *luaH_setnum (lua_State *L, Table *t, int key) {
	const TValue *p = luaH_getnum(t, key);
	if (p != luaO_nilobject)
		return cast(TValue *, p);
	else {
		TValue k;
		setnvalue(&k, cast_num(key));
		return newkey(L, t, &k);
	}
}


TValue *luaH_setstr (lua_State *L, Table *t, TString *key) {
	const TValue *p = luaH_getstr(t, key);
	if (p != luaO_nilobject)
		return cast(TValue *, p);
	else {
		// TODO 不理解以下两行的意义
		TValue k;
		setsvalue(L, &k, key);
		return newkey(L, t, &k);
	}
}
